﻿#define _CRT_SECURE_NO_WARNINGS
#include<string>
#include <iostream>
using namespace std;

// https://leetcode.cn/problems/add-strings/description/
//给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
//你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

//示例：
//输入：num1 = "456", num2 = "77"
//输出："533"



    //string addStrings(string num1, string num2)
    //{
    //    string addret;
    //    int p1 = num1.size() - 1;
    //    int p2 = num2.size() - 1;//需要支持跳出while的判断条件 用int类型
		  //addret.reserve(p1 > p2 ? p1 + 2 : p2 + 2);//提前扩容好(较大者的size+1) 避免后期扩容

    //    size_t sum = 0;
    //    size_t tens = 0;//记录进位
    //    size_t ones = 0;
    //    size_t value1 = 0;
    //    size_t value2 = 0;
    //    while (p1 >= 0 || p2 >= 0)
    //    {
    //        value1 = p1 < 0 ? 0 : num1[p1--] - '0';
    //        value2 = p2 < 0 ? 0 : num2[p2--] - '0';

    //        sum = value1 + value2 + tens;
    //        ones = sum % 10;
    //        addret += (ones + '0');//直接尾插 最后reserve 可提高效率
    //        tens = sum / 10;
    //    }
    //    if (tens)//还有进位
    //    {
    //        addret += (tens + '0');
    //    }

    //    reverse(addret.begin(), addret.end());

    //    return addret;
    //}
//
//
//int main()
//{
//
//    string num1 = "11";
//    string num2 = "123";
//    
//    string addret = addStrings(num1, num2);
//
//    cout << addret;
//	return 0;
//}








//https://leetcode.cn/problems/multiply-strings/description/
//给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
//注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
//示例 2:
//输入: num1 = "123", num2 = "456"
//输出 : "56088"




string addStrings(const string& num1, const string& num2)
{
    string addret;

    int p1 = num1.size() - 1;
    int p2 = num2.size() - 1;//需要支持跳出while的判断条件 用int类型

    addret.reserve(p1 > p2 ? p1 + 2 : p2 + 2);//提前扩容好(较大者的size+1) 避免后期扩容

    size_t sum = 0;
    size_t tens = 0;//记录进位
    size_t ones = 0;
    size_t value1 = 0;
    size_t value2 = 0;
    while (p1 >= 0 || p2 >= 0)
    {
        value1 = p1 < 0 ? 0 : num1[p1--] - '0';//如果其中有一位加完了(p1减到第0位之前) 补0
        value2 = p2 < 0 ? 0 : num2[p2--] - '0';

        sum = value1 + value2 + tens;
        ones = sum % 10;
        addret += (ones + '0');//直接尾插 最后reserve 可提高效率
        tens = sum / 10;
    }
    if (tens)//还有进位
    {
        addret += (tens + '0');
    }

    reverse(addret.begin(), addret.end());

    return addret;
}



string multiply(const string& num1, const string& num2)
{
    if (num1 == "0" || num2 == "0")//1.提高效率 2.避免结果出现多个0
    {
        return "0";
    }

    string mulret;

    string larger = num1;//不能给引用 引用不能改变指向
    string smaller = num2;
    if (num1.size() < num2.size())
    {
        larger = num2;
        smaller = num1;
    }

    //拆成分别算出较小者的每一位乘较大者(每升一位补一个零) 再相加

    size_t valueL = 0;
    size_t valueS = 0;

    size_t zero = 0;//补0的个数  //oj题会有循环测试 使用静态对象的时候 会影响下一次测试
    int pS = smaller.size() - 1;
    while (pS >= 0)
    {


        string sub_mulret;//记录每一个拆分后待相加的字符串 (作为临时变量 每一行都重新记)
        for (size_t i = 0; i < zero; i++)
        {
            sub_mulret += '0';//补0
        }

        size_t tens = 0;//记录进位
        size_t ones = 0;
        size_t valueMul = 0;
        valueS = smaller[pS] - '0';
        int pL = larger.size() - 1;
        while (pL >= 0)
        {
            valueL = larger[pL] - '0';
            valueMul = valueS * valueL + tens;
            ones = valueMul % 10;
            tens = valueMul / 10;
            sub_mulret += (ones + '0');

            pL--;
        }
        if (tens)//还有进位
        {
            sub_mulret += (tens + '0');
        }
        reverse(sub_mulret.begin(), sub_mulret.end());

        mulret = addStrings(mulret, sub_mulret);

        zero++;
        pS--;
    }

    return mulret;
}



//int main()
//{
//
//
//    string s1 = "999999999999999999999999999999999999999";
//    string s2 = "9999999999999999999999999999999999999999";
//
//    string s3 = multiply(s1, s2);
//    cout << string::npos << endl;
//    cout << s3;
//    return 0;
//}
//
//




//https://leetcode.cn/problems/first-unique-character-in-a-string/
//给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

class Solution {
public:
    int firstUniqChar(string s) //运用计数排序的思想
    {
        int count[26] = { 0 };//哈希表

        size_t sz = s.size();
        for (size_t i = 0; i < sz; i++)
        {
            count[s[i] - 'a']++;
        }

        for (size_t i = 0; i < sz; i++)
        {
            if (count[s[i] - 'a'] == 1)
            {
                return i;
            }
        }

        return -1;
    }
};





//https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/description/
//请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C / C++ 中的 atoi 函数）。

//函数 myAtoi(string s) 的算法如下：
//读入字符串并丢弃无用的前导空格
//检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
//读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
//将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
//如果整数数超过 32 位有符号整数范围[−2^31, 2^31 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
//返回整数作为最终结果。

//#define INT32_MAX 2^32 - 1
//#define INT32_MIN -2^32


//
//int myAtoi(string str)                                                          //版本1
//{
//    int ret = 0;
//    int signal = 1;
//    int signal_times = 0;//符号只能出现一次,并且要出现在数字前，防止"+-2"和"0-1"的情况
//    bool num_emerge = false;//数字后的所有非数字字符其余字符串
//    bool pre_space = true;
//    size_t end = str.size() - 1;
//    size_t i = 0;
//    while (i <= end)
//    {
//        while (str[i] == ' ')//去掉空格
//        {
//            if (num_emerge == false)
//            {
//                if (pre_space)
//                {
//                    ++i;
//                }
//                else
//                {
//                    return 0;//数字没出现 但是正负号出现了 "-   234"
//                }
//            }
//            else//数字出现了
//            {
//                return signal * ret;
//            }
//        }
//
//
//        if (str[i] == '-')
//        {
//            if (num_emerge)
//            {
//                return signal * ret;
//            }//下面两种情况证明数字没出现
//            else if (signal_times == 1)
//            {
//                return 0;
//            }
//            else
//            {
//                pre_space = false;
//                ++signal_times;
//                signal = -1;
//                ++i;
//            }
//        }
//        else if (str[i] == '+')
//        {
//            if (num_emerge)
//            {
//                return signal * ret;
//            }//下面两种情况证明数字没出现
//            else if (signal_times == 1)
//            {
//                return 0;
//            }
//            else
//            {
//                pre_space = false;
//                ++signal_times;
//                ++i;
//            }
//        }
//        else if (str[i] < '0' || str[i] > '9')//为前导字母
//        {
//            return signal * ret; //为后导字母时 也会直接返回已经计算好的ret
//        }
//        else //为数字字符
//        {
//            if (ret > INT32_MAX / 10)
//            {
//                return signal == 1 ? INT32_MAX : INT32_MIN;
//            }
//            else if (ret == INT32_MAX / 10 && (str[i] >= '7' && str[i] <= '9'))//INT32_MAX = 2147483647
//            {
//                if (signal == -1 && str[i] == '7')
//                {
//                    return signal * INT32_MAX;
//                }
//                return signal == 1 ? INT32_MAX : INT32_MIN;
//            }
//            else
//            {
//                pre_space = false;
//                num_emerge = true;
//                signal_times = 0;
//                ret = ret * 10 + (str[i++] - '0');
//            }
//
//        }
//
//    }
//    return signal * ret;
//
//}


class Solution                                                                  //版本2
{
public:
    int myAtoi(string str)
    {
        int ret = 0;
        int boundary = INT_MAX / 10;//防止很大的数字字符串
        int i = 0, sign = 1, length = str.size();
        if (length == 0)
        {
            return 0;
        }
        while (str[i] == ' ')//丢弃前导空格
        {
            if (++i == length) { return 0; }

        }
        if (str[i] == '-') { sign = -1; }//取前导空格之后的第一个正负号 不++
        if (str[i] == '+' || str[i] == '-') { i++; }//if -- 只跳过一个符号位 如果有两个(非法 eg：-+1) 后面循环里面就break了

        for (; i < length; ++i)//此时指针i遍历完前导空格和第一个符号位了
        {
            if (str[i] < '0' || str[i] > '9') { break; }//碰到非数字字符了
            //boundary = 214748364
            if (ret > boundary || ret == boundary && str[i] > '7')//INT32_MAX = 2147483647
            {
                return sign == 1 ? INT_MAX : INT_MIN;
            }

            ret = ret * 10 + (str[i] - '0');
        }
        return sign * ret;
    }
};



//
//int main()
//{
//
//
//    string s1 = "2147483646";
//    string s2 = "-91283472332";
//    string s3 = "    -88827   5655  U";
//
//    cout << myAtoi(s3.c_str()) << endl;
//    cout << atoi(s3.c_str()) << endl;
//
//    //cout << INT_MIN << endl;
//    return 0;
//}





//int main(int argc, char* argv[])
//{
//
//	string a = "hello world";
//
//	string b = a;
//
//	if (a.c_str() == b.c_str())
//
//	{
//
//		cout << "true" << endl;
//
//	}
//
//	else cout << "false" << endl;
//
//	string c = b;
//
//	c = "";
//
//	if (a.c_str() == b.c_str())
//
//	{
//
//		cout << "true" << endl;
//
//	}
//
//	else cout << "false" << endl;
//
//	a = "";
//
//	if (a.c_str() == b.c_str())
//
//	{
//
//		cout << "true" << endl;
//
//	}
//
//	else cout << "false" << endl;
//
//	return 0;
//
//}